package com.cn.zengzeng.spbzengzeng.service.sort;

/**
 * @Description: 排序种类
 * @Author: ZhangZengZeng
 * @Date: 2022/7/6 14:28
 */
public class SortDemo {

    public static final int [] num = {12,43,32,89,67,54,90,45,37};

    public static void main (String[] args) {
        maoPao(num);
        System.out.print("冒泡排序: ");
        bianLi(num);

        insertSort(num);
        System.out.print("插入排序: ");
        bianLi(num);
    }

    
    /**
    * @author ZhangZengZeng
    * @Description 遍历数组
    * @date 2022/7/6 14:45
    * @param array 数组
    */
    public static void bianLi(int[] array){
        for(int value : array) {
            System.out.print(value + " ");
        }
    }

    /**
    * @author ZhangZengZeng
    * @Description 每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。
     * 而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
    * @date 2022/7/6 14:41
    * @param array 待排数组
    */
    public static void maoPao(int[] array){
        int temp;
        for(int i = 0;i < array.length-1;i++) {//控制比较轮次，一共 n-1 趟
            for(int j = 0;j < array.length-1-i;j++) {//控制两个挨着的元素进行比较
                if(array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    public static void insertSort(int[] a){
        int length=a.length;//数组长度，将这个提取出来是为了提高速度。
        int insertNum;//要插入的数
        for(int i=1;i<length;i++){//插入的次数
            insertNum=a[i];//要插入的数
            int j=i-1;//已经排序好的序列元素个数
            while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格
                a[j+1]=a[j];//元素移动一格
                j--;
            }
            a[j+1]=insertNum;//将需要插入的数放在要插入的位置。
        }
    }

    public static void sheelSort(int[] a){
        int d  = a.length;
        while (d!=0) {
            d=d/2;
            for (int x = 0; x < d; x++) {//分的组数
                for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
                    int j = i - d;//j为有序序列最后一位的位数
                    int temp = a[i];//要插入的元素
                    for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。
                        a[j + d] = a[j];//向后移动d位
                    }
                    a[j + d] = temp;
                }
            }
        }
    }
}
